//
// Delaunay Triangulation
//
// Homework of CG lesson (Fall 2009) in Tsinghua University.
// All rights reserved.
//

#pragma once

#include "edge.h"

#include <vector>

using namespace std;

/**
 * Makes a new edge.
 */
Edge* makeEdge(void);
/**
 * This operator affects the two edge rings around the origins of a and b,
 * and, independently, the two edge rings around the left faces of a and b.
 * In each case, (i) if the two rings are distinct, Splice will combine
 * them into one; (ii) if the two are the same ring, Splice will break it
 * into two separate pieces.
 * Thus, Splice can be used both to attach the two edges together, and
 * to break them apart. See Guibas and Stolfi (1985) p.96 for more details
 * and illustrations.
 */
void splice(Edge* a, Edge* b);
/**
 * Deletes the edge @c e.
 */
void deleteEdge(Edge* e);
/**
 * Adds a new edge e connecting the destination of a to the
 * origin of b, in such a way that all three have the same
 * left face after the connection is complete.
 * Additionally, the data pointers of the new edge are set.
 */
Edge* connect(Edge* a, Edge* b);
/**
 * Essentially turns edge e counterclockwise inside its enclosing
 * quadrilateral. The data pointers are modified accordingly.
 */
void swap(Edge* e);
/**
 * Returns twice the area of the oriented triangle (a, b, c), i.e., the
 * area is positive if the triangle is oriented counterclockwise.
 */
double triarea(const Point2d& a, const Point2d& b, const Point2d& c);
/**
 * Returns TRUE if the point d is inside the circle defined by the
 * points a, b, c. See Guibas and Stolfi (1985) p.107.
 */
bool inCircle(const Point2d& a, const Point2d& b,
              const Point2d& c, const Point2d& d);
/**
 * Returns TRUE if the points a, b, c are in a counterclockwise order.
 */
bool ccw(const Point2d& a, const Point2d& b, const Point2d& c);
/**
 * @return true when the point @c x is to the right of the edge @c e.
 */
bool rightOf(const Point2d& x, Edge* e);
/**
 * @return true when the point @c x is to the left of the edge @c e.
 */
bool leftOf(const Point2d& x, Edge* e);
/**
 * A predicate that determines if the point x is on the edge e.
 * The point is considered on if it is in the EPS-neighborhood
 * of the edge.
 */
bool onEdge(const Point2d& x, Edge* e);
/**
 * test whether the edge e is above edge basel
 */
bool valid(Edge* e, Edge* basel);
/**
 * Returns an edge e either x is on e, or e is an edge of a triangle containing x.
 */
Edge* locate(const Point2d &x, Edge* startEdge);
/**
 * Tests whether two lines intersected, line1 defined by p1, p2, line2 defined by p3, p4
 */
bool lineIntersected(const Point2d& p1, const Point2d& p2, const Point2d& p3, const Point2d& p4);
/**
 * Returns edges which belongs to triangles which intersected by line defined by p1 and p2
 */
void intersectedTris(Point2d& p1, Point2d& p2, vector<Edge *>& edges, Edge* startEdge);
/**
 * Tests whether the point x is inside the triangles.
 */
bool testInside(const Point2d& x, Edge* startEdge);
/**
 * If point p1 is outside the triangles, search for the nearest intersect edge for p1.
 */
Edge* searchIntersectedEdge(Point2d& p1, Point2d& p2, Edge* startEdge);
/**
 * Calculates the parameters of circum circle for a specified triangle.
 */
void circumCircle(const Point2d& p1, const Point2d& p2, const Point2d& p3,
                  Point2d* pCenter, double* radius);
